package com.lims.algorithm.algset.graph.expression;

import org.apache.commons.collections4.CollectionUtils;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.function.Consumer;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * <功能简述> DAG有向无环图多任务执行引擎 —— 十字链表实现
 *
 * @author lims
 * @date 2020-11-22 17:26
 */
public class DgGraphEngine<T extends BaseVertexData> {
    /**
     * 日志
     */
    private static final Logger LOGGER = LoggerFactory.getLogger(DgGraphEngine.class);

    /**
     * 顶点集合索引失败返回
     */
    private static final int FAIL_INDEX_RETURN = -1;

    /**
     * 顶点类
     */
    class Vertex {
        // 数据
        T data;
        // 第一条边
        Edge firstEdge;
        // 第一条逆向边
        ReverseEdge firstRvsEdge;
        // 入度
        int inDegree;
        // 出度
        int outDegree;
        // 在图中的最大层级
        int levelMaxNum;

        public Vertex(T data, Edge firstEdge, ReverseEdge firstRvsEdge) {
            this.data = data;
            this.firstEdge = firstEdge;
            this.firstRvsEdge = firstRvsEdge;
        }

        // 入度加1
        public void incrInDegree() {
            inDegree++;
        }

        // 出度加1
        public void incrOutDegree() {
            outDegree++;
        }

        // 入度减1
        public void decrInDegree() {
            inDegree--;
        }

        // 出度减1
        public void decrOutDegree() {
            outDegree--;
        }

        public void incrLevelMaxNum() {
            levelMaxNum++;
        }

        public void decrLevelMaxNum() {
            levelMaxNum--;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "data=" + data +
                    ", firstEdge=" + firstEdge +
                    ", firstRvsEdge=" + firstRvsEdge +
                    '}';
        }
    }

    /**
     * 边 类
     */
    class Edge {
        // 指向的顶点
        int pVex;
        // 下一条边
        Edge nextEdge;
        // 边权重
        int weight;

        public Edge(int pVex, Edge nextEdge, int weight) {
            this.pVex = pVex;
            this.nextEdge = nextEdge;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "pVex=" + pVex +
                    ", nextEdge=" + nextEdge +
                    '}';
        }
    }

    /**
     * 逆向边 类（边的逆向表示，用于构造逆邻接表，十字链表）
     */
    class ReverseEdge {
        // 边来源顶点
        int rVes;
        // 下一条边
        ReverseEdge nextRvsEdge;
        // 边权重
        int weight;

        public ReverseEdge(int rVes, ReverseEdge nextRvsEdge, int weight) {
            this.rVes = rVes;
            this.nextRvsEdge = nextRvsEdge;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "ReverseEdge{" +
                    "rVes=" + rVes +
                    ", nextRvsEdge=" + nextRvsEdge +
                    ", weight=" + weight +
                    '}';
        }
    }

    /**
     * 最大值
     */
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 顶点集合
     */
    List<Vertex> vertexs;
    /**
     * 边数
     */
    int eNum;
    /**
     * 访问标记数组（是否被访问过）
     */
    boolean[] isVisited;
    /**
     * 边集合(key:边起点，value：边终点集合)
     */
    Map<Integer, List<Integer>> edgesMap;

    /**
     * 构造函数
     *
     * @param n 顶点数
     */
    public DgGraphEngine(int n) {
        vertexs = new ArrayList<>(n);
        eNum = 0;
        isVisited = new boolean[n];
        edgesMap = new ConcurrentHashMap<>();
    }

    /**
     * 无权的DAG构造方法
     *
     * @param versIn  顶点集合
     * @param edgesIn 边集合，Map中只保存一个键值对表示一条边，key：边起始点，value：边结束点
     */
    public DgGraphEngine(List<T> versIn, List<DgEdgeKvBean> edgesIn) {
        if (CollectionUtils.isEmpty(versIn)) {
            LOGGER.info("构建通用有向无环图失败--没有可用顶点");
            throw new RuntimeException("构建DAG图失败");
        }
        vertexs = new ArrayList<>(versIn.size());
        versIn.forEach(this::addVer);
        eNum = 0;
        isVisited = new boolean[versIn.size()];
        edgesMap = new ConcurrentHashMap<>();
        if (null != edgesIn) {
            edgesIn.forEach(edgeIn -> {
                // 边起始顶点
                String startEdgePoint = edgeIn.getStartEdgePoint();
                // 边结束顶点
                String endEdgePoint = edgeIn.getEndEdgePoint();
                if (null == startEdgePoint || null == endEdgePoint || startEdgePoint.equals(endEdgePoint)) {
                    LOGGER.error("******构建DAG图失败，边集合中键值对存在异常******");
                    throw new RuntimeException("构建DAG图失败");
                }
                addEdge(indexOfVertexsByKey(startEdgePoint), indexOfVertexsByKey(endEdgePoint), 1);
            });
        }
        //更新图中每个顶点的最大层级
        if (!setLevelUseTopological()) {
            // 构建有向图失败
            LOGGER.error("构建通用有向无环图失败--其中有环");
            throw new RuntimeException("构建DAG图失败");
        }
    }

    /**
     * 确定固定大小的访问标记数组
     *
     * @param n
     */
    public void fixIsVisited(int n) {
        isVisited = new boolean[n];
    }

    /**
     * 添加顶点
     *
     * @param ver 顶点的数据
     */
    public void addVer(T ver) {
        Vertex vertex = new Vertex(ver, null, null);
        vertexs.add(vertex);
    }

    /**
     * 添加边 v1 —— v2 （有向图）
     *
     * @param v1     边出来的结点
     * @param v2     边指向的结点
     * @param weight 边权重
     */
    public void addEdge(int v1, int v2, int weight) {
        // 已存在的边不添加，索引错误的边不添加
        if (v1 == FAIL_INDEX_RETURN || v2 == FAIL_INDEX_RETURN || isExistsEdge(v1, v2)) {
            return;
        }
        // v1指向v2的边
        Edge e2 = new Edge(v2, null, weight);
        // v1指向v2的逆向边
        ReverseEdge re2 = new ReverseEdge(v1, null, weight);

        //顶点v1
        Vertex vertex1 = vertexs.get(v1);
        //顶点v2
        Vertex vertex2 = vertexs.get(v2);

        // v1 —— v2边（v1顶点）
        if (vertex1.firstEdge == null) {
            vertex1.firstEdge = e2;
        } else {
            linkEdge(vertex1.firstEdge, e2);
        }
        // v1——v2逆向边（v2顶点）
        if (vertex2.firstRvsEdge == null) {
            vertex2.firstRvsEdge = re2;
        } else {
            linkRvsEdge(vertex2.firstRvsEdge, re2);
        }

        // v1顶点 出度 +1
        vertex1.incrOutDegree();
        // v2顶点 入度 +1
        vertex2.incrInDegree();

        // 边加入边集合
        List<Integer> pointEdges = edgesMap.get(v1);
        if (CollectionUtils.isNotEmpty(pointEdges)) {
            pointEdges.add(v2);
        } else {
            pointEdges = new ArrayList<>();
            pointEdges.add(v2);
            edgesMap.put(v1, pointEdges);
        }
        // 边数 +1
        eNum++;
    }

    /**
     * v1 -> v2 边是否存在
     *
     * @param v1
     * @param v2
     * @return
     */
    private boolean isExistsEdge(int v1, int v2) {
        List<Integer> pointEdges = edgesMap.get(v1);
        if (CollectionUtils.isNotEmpty(pointEdges)) {
            return pointEdges.contains(v2);
        }
        return false;
    }

    /**
     * 将边“tailEdge”链接到头为“firstEdge”的链表尾部
     *
     * @param firstEdge 链表头结点
     * @param tailEdge  需要链接的结点
     */
    private void linkEdge(Edge firstEdge, Edge tailEdge) {
        Edge edge = firstEdge;
        while (edge.nextEdge != null) {
            edge = edge.nextEdge;
        }
        edge.nextEdge = tailEdge;
    }

    /**
     * 将边“tailRvsEdge”链接到头为“firstRvsEdge”的链表尾部（逆向边）
     *
     * @param firstRvsEdge
     * @param tailRvsEdge
     */
    private void linkRvsEdge(ReverseEdge firstRvsEdge, ReverseEdge tailRvsEdge) {
        ReverseEdge rvsEdge = firstRvsEdge;
        while (rvsEdge.nextRvsEdge != null) {
            rvsEdge = rvsEdge.nextRvsEdge;
        }
        rvsEdge.nextRvsEdge = tailRvsEdge;
    }

    /**
     * 获取顶点
     *
     * @param index
     * @return
     */
    public Vertex getVertex(int index) {
        return vertexs.get(index);
    }

    /**
     * 返回顶点中的值
     *
     * @param index
     * @return
     */
    public T getValue(int index) {
        return vertexs.get(index).data;
    }

    /**
     * 返回<v1,v2>边的权重</>
     *
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1, int v2) {
        if (v1 >= vertexs.size() || v2 >= vertexs.size()) {
            return FAIL_INDEX_RETURN;
        }
        Edge edge = vertexs.get(v1).firstEdge;
        while (edge != null) {
            if (edge.pVex == v2) {
                return edge.weight;
            }
            edge = edge.nextEdge;
        }
        return FAIL_INDEX_RETURN;
    }

    /**
     * 下一个未访问过的邻接顶点
     *
     * @param index
     * @return
     */
    public int getNextAjcNoAccessVer(int index) {
        Vertex vertex = vertexs.get(index);
        Edge firstEdge = vertex.firstEdge;
        while (firstEdge != null) {
            if (!isVisited[firstEdge.pVex]) {
                return firstEdge.pVex;
            }
            firstEdge = firstEdge.nextEdge;
        }
        return FAIL_INDEX_RETURN;
    }

    /**
     * 重置图的访问标记数组
     */
    public void clearIsVisited() {
        isVisited = new boolean[vertexs.size()];
    }

    /**
     * 广度优先遍历
     */
    public void BfsTraversals(Consumer<T> consumer) {
        LOGGER.info("广度优先遍历执行：");
        for (int i = 0; i < vertexs.size(); i++) {
            if (!isVisited[i]) {
                BfsTraversals(isVisited, i, consumer);
            }
        }
    }

    protected void BfsTraversals(boolean[] isVisited, int i, Consumer<T> consumer) {
        // 队列头
        int h;
        // 邻接点
        int ajcVer;
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        consumer.accept(getValue(i));
        isVisited[i] = true;
        queue.offer(i);
        while (!queue.isEmpty()) {
            h = queue.poll();
            ajcVer = getNextAjcNoAccessVer(h);
            while (ajcVer != -1) {
                if (!isVisited[ajcVer]) {
                    consumer.accept(getValue(ajcVer));
                    isVisited[ajcVer] = true;
                    queue.offer(ajcVer);
                }
                ajcVer = getNextAjcNoAccessVer(h);
            }
        }
    }

    /**
     * 广度优先遍历并行执行同级任务
     */
    public void parallelSameLevelBfs(Consumer<List<T>> consumer) {
        LOGGER.info("---广度优先遍历执行DAG---");
        // 同一级顶点集合
        List<T> verParams = new ArrayList<>();
        for (int i = 0; i < vertexs.size(); i++) {
            if (!isVisited[i]) {
                parallelSameLevelBfs(isVisited, i, consumer, verParams);
            }
        }
    }

    protected void parallelSameLevelBfs(boolean[] isVisited, int i, Consumer<List<T>> consumer, List<T> verParams) {
        // 队列头
        int h;
        // 邻接点
        int ajcVer;
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        isVisited[i] = true;
        queue.offer(i);
        while (!queue.isEmpty()) {
            h = queue.poll();
            // 取出队列1次，加入执行入参listP一次
            verParams.add(getValue(h));
            // 加入执行层级的记录listRecord一次
            // 如果队列空 或者 h和队列头的层级不一致，则执行listP
            if (queue.isEmpty() ||
                    getVertex(h).levelMaxNum != getVertex(queue.peek()).levelMaxNum) {
                // 并行执行
                consumer.accept(verParams);
                verParams.clear();
            }
            ajcVer = getNextAjcNoAccessVer(h);
            while (ajcVer != -1) {
                if (!isVisited[ajcVer]) {
                    isVisited[ajcVer] = true;
                    queue.offer(ajcVer);
                }
                ajcVer = getNextAjcNoAccessVer(h);
            }
        }
    }

    /**
     * 对图进行反向依赖处理（即从叶子顶点开始，倒叙处理到头顶点为止）
     *
     * @param consumer
     */
    public void reverseProcessDepend(Consumer<T> consumer) {
        LOGGER.info("反向依赖处理图顶点--从叶子顶点依次向父顶点处理");
        // 辅助队列
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        // 初始化出度数组，记录每个顶点出度信息
        List<Integer> outDegrees = new ArrayList<>();
        vertexs.stream().forEach(vertex -> outDegrees.add(vertex.outDegree));
        // 初始化辅助队列，出度为0的点灌入队列
        Stream.iterate(0, t -> t + 1).limit(vertexs.size())
                .forEach(i -> {
                    if (0 == outDegrees.get(i)) {
                        queue.offer(i);
                    }
                });

        /*
        1.出度为0且未访问过顶点灌入辅助队列
        2.自定义函数式接口依次处理队列中顶点，处理完每个顶点对应父顶点出度减1（只修改出度数组，不修改顶点本身属性）
        3.下一轮出度为0且未访问过顶点入队列循环
         */
        // 有未访问顶点时循环执行
        while (!isAllVisited()) {
            while (!queue.isEmpty()) {
                // 顶点的索引
                int i = queue.poll().intValue();
                T data = vertexs.get(i).data;
                // 顶点数据处理逻辑
                consumer.accept(data);
                // 找到父顶点，将对应出度数组记录减1
                List<Integer> pointedVers = getPointedVer(data.getKey());
                pointedVers.stream().forEach(p -> outDegrees.set(p, outDegrees.get(p) - 1));
                // 已访问标记
                isVisited[i] = true;
            }
            // 所有顶点访问完退出
            if (isAllVisited()) {
                break;
            }
            // 出度标记为0且未访问过顶点入队列
            for (int i = 0; i < outDegrees.size(); ++i) {
                if (0 == outDegrees.get(i) && false == isVisited[i]) {
                    queue.offer(i);
                }
            }
        }
    }

    /**
     * 所有顶点都已访问过
     *
     * @return
     */
    public boolean isAllVisited() {
        // 有未访问顶点返回false
        for (boolean visited :
                isVisited) {
            if (visited == false) {
                return false;
            }
        }
        return true;
    }

    /**
     * 设置顶点是否为叶子顶点
     */
    public void setVerIsLeaf() {
        vertexs.stream().forEach(v -> {
            if (0 == v.outDegree) {
                v.data.setIsLeaf(true);
            }
        });
    }

    /**
     * 拓扑排序：
     * （将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。）
     * <p>
     * 步骤：
     * 1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological)；
     * 2. 把所有没有依赖顶点的节点放入Q；
     * 3. 当Q还有顶点的时候，执行下面步骤：
     * 3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)；
     * 3.2 对n每一个邻接点m(n是起点，m是终点)；
     * 3.2.1 去掉边<n,m>;
     * 3.2.2 如果m没有依赖顶点，则把m放入Q;
     * 注：顶点A没有依赖顶点，是指不存在以A为终点的边。
     *
     * @return 返回值
     * *    -1 -- 失败(由于内存不足等原因导致)
     * *     0 -- 成功排序，并输入结果
     * *     1 -- 失败(该有向图是有环的)
     */
    public int topologicalSort() {
        if (!graphIsDAG()) {
            return 1;
        }
        // 拓扑排序结果
        List<T> tops = new ArrayList<>();
        // 顶点入度数组
        List<Integer> inDegrees = new ArrayList<>();
        vertexs.stream().forEach(vertex -> inDegrees.add(vertex.inDegree));
        // 辅助队列
        Queue<Integer> queue = new LinkedBlockingQueue<>();

        // 入度为0的顶点入队列
        Stream.iterate(0, t -> t + 1).limit(inDegrees.size())
                .forEach(i -> {
                    if (0 == inDegrees.get(i)) {
                        queue.offer(i);
                    }
                });

        while (!queue.isEmpty()) {
            int j = queue.poll().intValue();
            tops.add(vertexs.get(j).data);
            Edge firstEdge = vertexs.get(j).firstEdge;
            while (firstEdge != null) {
                inDegrees.set(firstEdge.pVex, inDegrees.get(firstEdge.pVex) - 1);
                if (0 == inDegrees.get(firstEdge.pVex)) {
                    queue.offer(firstEdge.pVex);
                }
                firstEdge = firstEdge.nextEdge;
            }
        }

        // 打印拓扑排序结果
        LOGGER.info("DAG拓扑排序结果:{}", tops);
        return 0;
    }

    /**
     * 判断图是否是DAG
     */
    public boolean graphIsDAG() {
        // 顶点入度数组
        List<Integer> inDegrees = new ArrayList<>();
        vertexs.stream().forEach(vertex -> inDegrees.add(vertex.inDegree));

        // 辅助队列
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        // 入度为0的顶点入队列
        Stream.iterate(0, t -> t + 1).limit(inDegrees.size())
                .forEach(i -> {
                    if (0 == inDegrees.get(i)) {
                        queue.offer(i);
                    }
                });

        while (!queue.isEmpty()) {
            // 出队列
            int j = queue.poll().intValue();
            Edge firstEdge = vertexs.get(j).firstEdge;
            // 对邻接点入度 -1
            while (firstEdge != null) {
                inDegrees.set(firstEdge.pVex, inDegrees.get(firstEdge.pVex) - 1);
                if (0 == inDegrees.get(firstEdge.pVex)) {
                    queue.offer(firstEdge.pVex);
                }
                firstEdge = firstEdge.nextEdge;
            }
        }

        // 入度为0的顶点数
        int zeroDegreeNum = inDegrees.stream().filter(i -> 0 == i).collect(Collectors.toList()).size();
        if (vertexs.size() > zeroDegreeNum) {
            return false;
        }
        return true;
    }

    /**
     * 利用拓扑排序设置顶点最大层级
     * <p>
     * 拓扑结果tops 入度数组inDgrees,步骤：
     * * 1.入度为0的点入队列
     * * 2.队列投h出队列，并给h出度的邻接点的入度 -1，如果-1后入度为0，则入队列
     *
     * @return *
     * *     true -- 成功排序，并输入结果
     * *     false -- 失败(该有向图是有环的)
     */
    public boolean setLevelUseTopological() {
        if (!graphIsDAG()) {
            return false;
        }
        // 拓扑排序结果
        List<T> tops = new ArrayList<>();
        // 辅助队列
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        // 顶点入度数组
        List<Integer> inDegrees = new ArrayList<>();
        vertexs.stream().forEach(vertex -> inDegrees.add(vertex.inDegree));

        // 入度为0的顶点入队列（PS：并不是真的将顶点的入度进行修改，而是只更改入度辅助数组）
        Stream.iterate(0, t -> t + 1).limit(inDegrees.size())
                .forEach(i -> {
                    if (0 == inDegrees.get(i)) {
                        queue.offer(i);
                    }
                });

        while (!queue.isEmpty()) {
            int j = queue.poll().intValue();
            tops.add(vertexs.get(j).data);
            // 更新顶点的最大层级 （拓扑排序到入度为0的顶点，说明前面依赖顶点都已遍历）
            vertexs.get(j).levelMaxNum = parMaxLevel(vertexs.get(j)) + 1;
            Edge firstEdge = vertexs.get(j).firstEdge;
            // 对指向顶点的入度全部减1，并将入度为0的顶点入队列
            while (firstEdge != null) {
                inDegrees.set(firstEdge.pVex, inDegrees.get(firstEdge.pVex) - 1);
                // 入度为0的时候入队列
                if (0 == inDegrees.get(firstEdge.pVex)) {
                    queue.offer(firstEdge.pVex);
                }
                firstEdge = firstEdge.nextEdge;
            }
        }

        // 打印拓扑排序结果
        LOGGER.info("DAG拓扑排序结果:{}", tops);
        return true;
    }

    /**
     * 更新顶点v的最大层级
     *
     * @param v
     * @return
     */
    private int parMaxLevel(Vertex v) {
        if (v == null) {
            return 0;
        }
        ReverseEdge firstRvsEdge = v.firstRvsEdge;
        int levelMaxNum = 0;
        while (firstRvsEdge != null) {
            Vertex vertex;
            int parLevelNum = (vertex = getVertex(firstRvsEdge.rVes)) != null ? vertex.levelMaxNum : 0;
            levelMaxNum = levelMaxNum < parLevelNum ? parLevelNum : levelMaxNum;
            firstRvsEdge = firstRvsEdge.nextRvsEdge;
        }
        return levelMaxNum;
    }

    /**
     * Dijkstra最短路径。(每次确定一个点最短路径后，比较经过此条最短路径到这个点邻接点的路径和原来到邻接点的路径，取最小值)
     * 源点v、确定距离标记数组st[]、距离数组distance[]
     * <p>
     * 1.初始化数组
     * 2.遍历找i -> j的距离
     * 2.1 每次找到未确定点的最短距离，确定一个顶点 w
     * 2.2 更新 w 有出度影响到的顶点的距离
     *
     * @param v 源点
     * @return 最小路径到达下标结点时的前一个结点下标（记录最短路径中的详细结点）（每次确定距离的点i，i下游受影响，下游前结点为i）
     */
    public int[] dijkstra(int v) {
        if (v < 0 || v > vertexs.size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // 确定距离标记数组
        boolean[] st = (boolean[]) Array.newInstance(boolean.class, vertexs.size());
        // 距离数组
        int[] distance = (int[]) Array.newInstance(int.class, vertexs.size());
        // 最短路径中的点的前一个点下标
        int[] minPointPre = (int[]) Array.newInstance(int.class, vertexs.size());

        distance = Arrays.stream(distance).map(d -> d = INF).toArray();
        Stream.iterate(0, t -> t + 1).limit(minPointPre.length)
                .forEach(i -> minPointPre[i] = -1);

        // 1.初始化距离和标记数组
        distance[v] = 0;
        Edge curEdge = vertexs.get(v).firstEdge;
        while (curEdge != null) {
            distance[curEdge.pVex] = curEdge.weight;
            minPointPre[curEdge.pVex] = v;
            curEdge = curEdge.nextEdge;
        }
        st[v] = true;

        // 2.遍历 到j的距离
        for (int i = 0; i < distance.length; ++i) {
            int min = INF;
            int index = -1;

            // 2.1找到未确定的最短距离
            for (int j = 0; j < distance.length; ++j) {
                if (!st[j] && distance[j] < min) {
                    min = distance[j];
                    index = j;
                }
            }

            // 2.2 更新j出度邻接点受影响的距离
            dijkstraUpdateDist(st, distance, minPointPre, index, min);
        }

        LOGGER.info("最短距离（源点{}）:{}", v, Arrays.toString(distance));

        return minPointPre;
    }

    /**
     * dijkstra 更新j出度邻接点受影响的距离
     *
     * @param st
     * @param distance
     * @param minPointPre
     * @param index
     * @param min
     */
    private void dijkstraUpdateDist(boolean[] st, int[] distance, int[] minPointPre, int index, int min) {
        if (index != -1) {
            st[index] = true;
            Edge outgreeEdge = vertexs.get(index).firstEdge;
            while (outgreeEdge != null) {
                if (!st[outgreeEdge.pVex] &&
                        (min + outgreeEdge.weight) < distance[outgreeEdge.pVex]) {
                    // 新确定点的出度影响了邻接点距离 更新最短距离
                    distance[outgreeEdge.pVex] = min + outgreeEdge.weight;
                    // 记录最短路径中本点的前一个结点，确定点index，本点为index的下一个邻接点
                    minPointPre[outgreeEdge.pVex] = index;
                }
                outgreeEdge = outgreeEdge.nextEdge;
            }
        }
    }

    /**
     * 查询ver在顶点集合中的索引
     *
     * @param ver
     * @return
     */
    public int indexOfVertexsByData(T ver) {
        for (int i = 0; i < vertexs.size(); ++i) {
            if (ver.getKey().equals(vertexs.get(i).data.getKey())) {
                return i;
            }
        }
        return FAIL_INDEX_RETURN;
    }

    /**
     * 通过key查询对应顶点在顶点集合中的索引
     *
     * @param key
     * @return
     */
    public int indexOfVertexsByKey(String key) {
        for (int i = 0; i < vertexs.size(); ++i) {
            if (key.equals(vertexs.get(i).data.getKey())) {
                return i;
            }
        }
        return FAIL_INDEX_RETURN;
    }

    /**
     * 根据顶点Key查询所有依赖key顶点的顶点集合
     *
     * @param key
     * @return 顶点key的形式接收
     */
    public List<String> getPointVerKeys(String key) {
        int i = indexOfVertexsByKey(key);
        List<String> pointVers = new ArrayList<>();
        if (i != FAIL_INDEX_RETURN) {
            Vertex vertex = vertexs.get(i);
            Edge firstEdge = vertex.firstEdge;
            while (firstEdge != null) {
                pointVers.add(getValue(firstEdge.pVex).getKey());
                firstEdge = firstEdge.nextEdge;
            }
        }
        return pointVers;
    }

    /**
     * 根据顶点Key查询所有依赖key顶点的顶点集合
     *
     * @param key
     * @return 以顶点在数组中索引形式返回
     */
    public List<Integer> getPointVers(String key) {
        int i = indexOfVertexsByKey(key);
        List<Integer> pointVers = new ArrayList<>();
        if (i != FAIL_INDEX_RETURN) {
            Vertex vertex = vertexs.get(i);
            Edge firstEdge = vertex.firstEdge;
            while (firstEdge != null) {
                pointVers.add(firstEdge.pVex);
                firstEdge = firstEdge.nextEdge;
            }
        }
        return pointVers;
    }

    /**
     * 根据顶点Key查询key对应顶点依赖的顶点的集合（指向key顶点的顶点）
     *
     * @param key
     * @return 顶点集中索引表示
     */
    public List<Integer> getPointedVer(String key) {
        int i = indexOfVertexsByKey(key);
        List<Integer> pointedVers = new ArrayList<>();
        if (i != FAIL_INDEX_RETURN) {
            Vertex vertex = vertexs.get(i);
            ReverseEdge firstRvsEdge = vertex.firstRvsEdge;
            while (firstRvsEdge != null) {
                pointedVers.add(firstRvsEdge.rVes);
                firstRvsEdge = firstRvsEdge.nextRvsEdge;
            }
        }
        return pointedVers;
    }

    /**
     * 返回指定层级的所有顶点
     *
     * @param levelNum
     * @return
     */
    public List<Vertex> getVertexsByLevel(int levelNum) {
        List<Vertex> vers = new ArrayList<>();
        if (levelNum <= 0) {
            LOGGER.error("dag图中查找相同层级顶点入参小于零错误");
            return vers;
        }
        vers = vertexs.stream().filter(vertex -> levelNum == vertex.levelMaxNum).collect(Collectors.toList());
        return vers;
    }

    /**
     * 以顶点值的形式返回指定层级的所有顶点
     *
     * @param levelNum
     * @return
     */
    public List<T> getVertexValByLevel(int levelNum) {
        List<Vertex> vertexsByLevel = getVertexsByLevel(levelNum);
        List<T> vertexsVal = new ArrayList<>();
        if (CollectionUtils.isEmpty(vertexsByLevel)) {
            LOGGER.error("dag图中查找相同层级顶点为空");
            return vertexsVal;
        }
        vertexsByLevel.forEach(vertex -> vertexsVal.add(vertex.data));
        return vertexsVal;
    }

    /**
     * 显示十字链表
     */
    public void show() {
        LOGGER.info("十字链表显示：{}", vertexs);
    }
}











